package code.oldCode.classic150;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author cuihaoran
 * @date 2024/12/17
 */
public class Classic150_interval {
    /* 228. 汇总区间 */
    public List<String> summaryRanges(int[] nums) {
        int len = nums.length;
        List<String> list = new ArrayList<>();
        if (len == 0)
            return list;
        int nowBegin = nums[0];
        int now = nums[0];
        for (int i = 1; i < len; i++) {
            // 如果和上一个不连续
            if (nums[i] - now != 1) {
                String sb = nowBegin == now ? String.valueOf(now) : nowBegin + "->" + now;
                list.add(sb);
                nowBegin = nums[i];
            }
            now = nums[i];
        }
        // 最后一个
        String sb = nowBegin == now ? String.valueOf(now) : nowBegin + "->" + now;
        list.add(sb);

        return list;
    }

    /* 56. 合并区间 */
    public int[][] merge(int[][] intervals) {
        // 排序
        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[0] != o2[0])
                return Integer.compare(o1[0], o2[0]);
            else
                return Integer.compare(o1[1], o2[1]);
        });
        int n = intervals.length;
        List<int[]> list = new ArrayList<>();
        int[] temp = new int[2];
        temp[0] = intervals[0][0];
        temp[1] = intervals[0][1];
        for (int i = 1; i < n; i++) {
            if (intervals[i][0] <= temp[1]) {
                temp[1] = Math.max(temp[1], intervals[i][1]);
            } else {
                list.add(temp);
                temp = new int[2];
                temp[0] = intervals[i][0];
                temp[1] = intervals[i][1];
            }
        }
        list.add(temp);
        int[][] ans = new int[list.size()][2];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    /* 57. 插入区间 */
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int len = intervals.length;
        // 长度为0，返回新的
        if (len == 0)
            return new int[][]{newInterval};
        // 得到包含的左面和右面的位置，其中右面的位置指向下一个，即intervals[leftPos, rightPos)
        int leftPos = getBinaryPos(intervals, newInterval[0], true);
        int rightPos = getBinaryPos(intervals, newInterval[1], false);
        // 如果leftPos==rightPos，说明newInterval是单独的一个区间
        // 如果leftPos!=rightPos，说明newInterval涵盖了有关intervals[ [leftPos,rightPos) ]
        List<int[]> list = new ArrayList<>();
        int nowPos = 0;
        boolean isOK = false; // leftPos==rightPos时设为true
        while (nowPos < len) {
            // 当nowPos != leftPos时或处理完leftPos == rightPos时，直接加入
            if (nowPos != leftPos || isOK) {
                list.add(intervals[nowPos]);
                nowPos++;
            }
            // 当nowPos == leftPos时
            else {
                if (leftPos == rightPos) {
                    list.add(newInterval);
                    isOK = true;
                } else {
                    int tempLeft = Math.min(newInterval[0], intervals[leftPos][0]);
                    int tempRight = Math.max(newInterval[1], intervals[rightPos - 1][1]);
                    list.add(new int[]{tempLeft, tempRight});
                    nowPos = rightPos;
                }
            }
        }
        // 特殊情况，若newInterval在最后插入
        if (leftPos == rightPos && leftPos == len) {
            list.add(newInterval);
        }
        // 生成答案
        int[][] ans = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }

        return ans;
        // 官解没用二分查找提前找位置，直接遍历intervals[][]的每个interval[]，与newInterval有交集则处理，无交集则加入，更好实现。
    }

    public int getBinaryPos(int[][] intervals, int num, boolean isLeft) {
        int left = 0, right = intervals.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (intervals[mid][0] <= num && num <= intervals[mid][1]) {
                return isLeft ? mid : mid + 1; // 右面数字的插入位置，就算命中，也指向下一个
            } else if (num < intervals[mid][0]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left; // 插入位置
    }

    /* 452. 用最少数量的箭引爆气球 */
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (o1, o2) -> {
            if (o1[0] != o2[0])
                return Integer.compare(o1[0], o2[0]);
            else
                return Integer.compare(o1[1], o2[1]);
        });
        int[] nowRange = new int[]{points[0][0], points[0][1]};
        int ans = 1;
        for (int i = 1; i < points.length; i++) {
            // 如果没有交集，代表上一次已经结束了
            if (nowRange[1] < points[i][0]) {
                ans++;
                nowRange = points[i];
            }
            // 如果有交集，计算交集
            else {
                nowRange[0] = Math.max(nowRange[0], points[i][0]);
                nowRange[1] = Math.min(nowRange[1], points[i][1]);
            }
        }

        return ans;
    }
}
